Navigation systems contain certain required basics: input/output device(s); a processing unit, a navigation calculation core; geographic database usually including streets and Points of Interest (“POIs”); and a Global Positioning System chip-set to determine position; inter alia. For automotive systems, there is additionally a gyroscopic chip that provides heading and speed information. Significant disadvantages exist with current systems. Navigation systems built into vehicles by the OEMS require expensive hardware and software, which becomes obsolete far sooner than the car in which it is installed. Additionally, the on-board geographic database requires a storage medium, such as a hard-drive, which, relatively, are more prone to failure than other electronics components, and the database must be updated periodically.
Server-based navigation systems are those in which guidance algorithm is resident on a central processing unit or server. End users input navigation destinations using a variety of devices, including mobile phones, computers, portable navigation devices, embedded vehicle systems and mobile data terminals (“MDT”). The end user request is communicated to the server wirelessly, either via a mobile phone network, a satellite network, a Wi-Fi network, or mixed network containing both wireless and wired connections. The wireless link can be interrupted in a number of circumstances (e.g., tunnels, concrete canyons in the centers of major cities, in unpopulated areas, and at times of heavy wireless usage). Depending on how the system was configured, the amount of data that needs to be transmitted often overwhelms the wireless resource. Cellphone and personal navigation are similarly limited.
In any geographic region, there are a small number of sources for the navigation database information, itself. A navigation database will provide coordinates and names for streets, as well as defining a street-type for each road (e.g., residential, commercial, highway, interstate, etc.). Often, the navigation database will also include points of interest (“POIs”), which are local business, places of civic or historic significance, schools, churches, and other places frequented by the public. In the United States, the U.S. Census Bureau offers Topologically Integrated Geographic Encoding and Referencing system data (“TIGER data”). TIGER data does not contain a complete set of navigatable streets in the U.S., nor does it provide POIs. There are multiple commercial providers of navigation databases, who provide POIs and a substantially complete set of navigatable streets. The two largest, in the United States, are Navteq® and Tele Atlas®. Unless the text is specifically contrary, the use of POIs in this patent means the general idea of points of interests, rather than any specific, discrete collection of points of interests. In Korea and Japan, the navigation databases are government controlled. Other jurisdictions range from government-owned to private services providing the navigation databases. Additional navigation and navigation database competitors are rapidly entering the market, including Apple and Google. Additionally, the crowdsourcing revolution is impacting map databases. For example, MapBox is working on an open-source collaborative map database called OpenStreetMap. In general, at this point, almost all vehicular and mobile phone navigation relies on navigation software from one source, and a complimentary navigation database from another source. Almost always, a single entity bundles and sells the navigations components as a complete solution.
Despite its limitations, the last two decades have seen a proliferation of advanced electronics aimed at navigation. Two decades ago, most vehicles had very little electronic content, and cellphone or mobile phones were in their infancy. Today, the revolution in vehicle and wireless electronics has made global-positioning based navigation ubiquitous. However, the proliferation of options for consumers has not presented an optimized overall solution, yet. Most navigation solutions rely on computational cores which are more than a decade old.
All current navigation algorithms rely on one-dimensional optimization. All streets are represented by vectors of varying length and shape. Fundamentally there are two ways the current methods represent streets. In the first, all vectors are straight line vectors. Curves are decomposed into a number of straight line segments. In the second, curves and splines of one form or another are used to mimic the natural curvature of the roads.
In order to find a route, current algorithms piece-wise optimize in one dimension. Many individual algorithms exist to perform one-dimensional piece-wise navigation optimization, including, but not limited to, single-sided decision tree, double-sided decision tree, single-sided decision tree with gates, double-sided decision tree with gates, buckets, and leaky buckets. Multiple route segments are grown from either the origin or both the origin and the destination. The routes are compared with one another during the process, and a single or multiple rejection criteria are established to discard divergent solutions. Ultimately, a single route is grown between the origin and the destination, either meeting in the middle (in the case of piece-wise solutions growing from both the origin and the destination) or at the destination (in the case of piece-wise solutions growing only from the origin). Strangely enough, if the process was truly piece-wise optimizing a solution, it would be irrelevant for calculation purposes whether the algorithm started at the origin or the destination. In many algorithms, the calculation will pick different routes in a single-sided decision when the origin and destination are reversed. Some algorithms correct for this by calculating both routes and then presenting the more efficient or optimized route to the end user.
The process is facilitated by road weighting. Essentially, interstates and other highways are more highly weighted than major surface thoroughfares. Major surface roads are weighted more heavily than paved secondary roads, which, in turn, are weighted more heavily than residential streets. The weighting combines with the piece-wise, one-dimensional optimization to select a route between any origin and destination. Unfortunately, such weighting often ends up with “interstate bias.” Many users of navigation systems have noted that the systems tend to prefer interstate or highway routes, even when they are significantly detour from the straight line between the origin and destination.
The major characterization to take away about today's technology is that it creates routes using piece-wise optimization and weighting. It does not create explicit solutions, even in the relatively local area, even though modern processors and algorithms would easily allow explicit local solutions. Piece-wise optimization and weighting creates a bias towards interstate or highway travel. Such antiquated computational cores create legacy artifacts, which substantially affects the performance of today's navigation systems. These cores were written for slow processors, such as the first generation of RTOS processors. These cores assumed a much smaller volume of data than what can currently be handled (e.g., petabyte systems). These cores assumed that wireless data transfer, if any, would be at substantially slower speeds than what is currently capable.
This is not to say that companies have not been updating their software over the past twenty years. What it means is that, when a piece of core software is initially written, many limitations are inherently built-in, either through commission or omission, which makes it difficult to create an update which is truly up-to-date. Additionally, when re-envisioning their software, most software teams have unstated (often unconscious) pre-conceptions about what is possible, because they are starting from a knowledge-base that includes their legacy code.
The legacy artifacts caused by antiquated navigational cores include inaccurate estimated-time-of-arrival (“ETA”) calculations, lack of learning, inability to handle multi-vehicle/multi-destination problems with the same software that is used for normal navigation, inability to optimize the solution for multi-vehicle/multi-destination problems, the inability to reasonably assess when the user has substantially diverted from the calculated route, and the inability to pass navigation back-and-forth between devices (e.g., between an in-car unit and a cellphone).
Most navigation systems are capable of giving an ETA with a 10% error rate, or less, 80-90% of the time. Most consumers are satisfied with this because (1) they don't rely on the ETA information as their only estimate of their arrival time; (2) the ETA information is better information than what they have from other sources; and/or (3) end-users have normalized their expectations to the system performance level available. However, there are categories of users for whom the error rate is strictly unacceptable. For example, commercial vehicle drivers, commercial fleet operators, people on a tight deadline, and people living in congested areas (where current technology under-performs).
Poor ETAs are partially related to the inability of current navigation cores to learn in any meaningful sense. For example, most people know that on Monday morning (excluding holidays), Interstate 405 in Los Angeles is going to be congested at 8:00 a.m. Current navigation cores do not. Likewise, I-696 in metropolitan Detroit, I-90/94 in Chicago, I-95 in Boston, and many other major interstates in major cities are routinely congested. Travel speeds at rush hour on these roads can vary between 60 m.p.h. and 10 m.p.h., on average. Much of the variation is entirely predictable: particular times, days, and conditions are particularly bad, such as Friday afternoons and rain. Unfortunately, current navigation solutions are unable to assess this situation a priori.
Current systems attempt to mask this problem with “dynamic navigation.” Dynamic navigation usually entails using “real-time” traffic data, at an additional cost to the user, to re-route the user if there is congestion. Realistically speaking, there is nothing dynamic about dynamic navigation. Most “real-time” traffic reports have a latency of 20 minutes or more, and come from a single source. With little or no motivation to improve performance in a monopolized field, traffic data fed into dynamic navigation systems is atrophying. Moreover, routinely starting a route towards traffic congestion, only to be re-routed when the navigation system's weighting function finally calculates an actionable event from real-time traffic messaging system, creates a big issue, costs the end-user time, money, and tranquility.
None of the current navigation systems handle multi-vehicle/multi-destination problems. Rather, fleet owners and others who are in need of such service must purchase both a navigation package and a dispatch package, or purchase a dispatch package with an embedded navigation package. These solutions are more antiquated than the traditional navigation cores. They also fail to realize that the multi-vehicle/multi-destination navigation solution is just a mathematical generalization of the single-vehicle/single-destination problem. In fact, most of the current navigation packages can now perform a single vehicle navigation to multiple destinations. Unfortunately, it is doing it in a linear piece-wise method (computationally inefficient and ineffective), rather than in an integrated fashion (computationally efficient and effective).
The commercially available dispatch systems which attempt to solve the multiple vehicle/multiple destinations problems do a poor job. In fact, in many market segments, such as vehicles for hire, users prefer performing these activities by hand, because the output from commercially available software is so sub-optimal that it represents a larger cost than performing the activities by hand.
The poor solutions for multi-vehicle, multi-destination navigation pose numerous costs to the users and to society. For example, large fleet owners, who use products with 10% error for their ETA, routinely have to choose between having more vehicle than needed on a given day (added expense) or loosening service standards (losing customers). For many people, this problem presents itself during in-home service calls. Cable companies, phone companies, and repair personnel routinely tell people generalized times, such as 9 a.m. to noon, rather than giving a more precise time. This leads to frustrated consumers and a loss of business (people, out of necessity, have to forego the service call).
Most people have learned preferred routes near their homes and businesses. These preferred routes offer the user a quicker and/or more convenient route. If a user continually traverses a preferred route, current navigation cores are incapable of incorporating the data in a meaningful way.
There are some solutions on the market that attempt to mask this inadequacy, by “learning” a preferred route. However, the way these systems work, the user has to travel between point A and point B. With repetition, the system will learn preferred sub-routes on which to guide the user between point A and point B. However, the systems are unable to generalize this information in a way which is useful to the end user. Most users would find dubious value in a system that will tell them the route they should take, after they have taken that route three or four times. What users desire is a way to take information, such as the avoidance of traffic control devices, particular ways into or out of business parks, shopping centers and residential sub-divisions, and generalize the information to all other route guidance performed by the unit.
The commercially available navigation software cores all have issues when it comes to reasonably re-routing people. In most systems, any divergence from the calculated route will cause the system to re-calculate a solution, which will essentially get the user back onto the originally calculated route. These re-calculations usually entail back-tracking, zigzagging, or returning the user, immediately, to the original route. There is no provision possible for small divergences from the proposed route, seamlessly re-introducing the user into the originally propose route at a reasonable distance.
Current navigation systems also lack interoperability. An end-user may have one system in their car, one on their laptop, and one on their cellphone. However, with few exceptions, little data can be passed from one to another. Additionally, it is impossible to start a navigation on a cellphone, enter into a vehicle, and have the vehicle's navigation system provide the navigation calculated on the cellphone.